---
title: "next_permutation"
created: 2025-11-28
tags:
  - 算法
---

# next_permutation

`std::next_permutation` 是 C++ 标准库中的一个函数，用于生成给定序列的下一个字典序排列。如果可能，它会重新排列序列中的元素，形成下一个更大的排列，并返回 `true`。如果这个序列已经是最大的排列，则将其重置为最小的排列（即升序排列），并返回 `false`。这个函数定义在 `<algorithm>` 头文件中。

### 基本用法

```
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
```

- `first` 和 `last` 是双向迭代器，分别指向序列的开始和结束。

### 示例

#### 对 `std::vector` 使用 `next_permutation`

```cpp
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3};

    std::cout << "{1, 2, 3}的全排列为：\n";
    do {
        for (int num : vec) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    } while (std::next_permutation(vec.begin(), vec.end()));

    return 0;
}

/*
{1, 2, 3}的全排列为：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/
```

这段代码会打印出 `{1, 2, 3}` 的所有排列。

#### 对字符串使用 `next_permutation`

```typescript
#include <algorithm>
#include <iostream>
#include <string>

int main() {
    std::string str = "abc";

    std::cout << "\"abc\" 的全排列为：\n";
    do {
        std::cout << str << "\n";
    } while (std::next_permutation(str.begin(), str.end()));

    return 0;
}

/*
"abc" 的全排列为：
abc
acb
bac
bca
cab
cba
*/
```

这段代码会打印出 `"abc"` 的所有排列。

### 注意事项

- 在第一次调用 `next_permutation` 前，序列应该处于想要开始的排列顺序。

  如果你希望遍历所有可能的排列，确保序列是按字典序最小（即**升序**）排列的。
- `next_permutation` 不仅可以用于数字的排列，还可以用于任何支持比较操作的元素类型的序列，包括字符、字符串等。
- 这个函数在使用时不需要额外的存储空间，它直接在原地修改序列。

`std::next_permutation` 是一个非常实用的工具，能够帮助解决排列组合相关的问题，比如寻找字典序的下一个排列、遍历一个集合的所有排列等。由于它的实现考虑了字典序的规则，因此可以有效地用于算法竞赛、问题求解等场景。

---
⬅️ [[isalpha-isdigit|isalpha-isdigit]] 🏠 [[00-刷题理模型]] ➡️ [[ascii基础 getline|ascii基础 getline]]